# -*- coding: utf-8 -*-

"""剑指 Offer II 002. 二进制加法
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。"""

class Solution:
    """方案1：
    先将二进制字符串全部转为二进制整数，转为十进制整数求和，转为二进制整数，转化为字符串，全部通过python内置函数实现
    
    方案2：
    从尾巴开始，逐位往前计算，每次计算有3个数字符， 'ai', 'bi', 'carry_bit'，需要求得2的余数和商，因为都是字符，可以用枚举法，状态机法，查表法，综合执行效率来看，还是查表法最快
    至于最后结果保存，可以先申请一个可以容纳结果的列表，如a,b两个加数的最大长度+1的空白数组，最后最多删除首部一位，可以避免列表反转操作"""
    calculate = {
        # 'ai-bi-cb': ('r', 'pre_cb')
        '000': ('0', '0'),
        '001': ('1', '0'),
        '010': ('1', '0'),
        '011': ('0', '1'),
        '100': ('1', '0'),
        '101': ('0', '1'),
        '110': ('0', '1'),
        '111': ('1', '1'),
    }

    def addBinary(self, a: str, b: str) -> str:
        lna, lnb = len(a), len(b)
        ai, bi, cb = lna-1, lnb-1, '0'
        nums = ['',] * (max(lna, lnb)+1)
        ni = len(nums)-1
        while True:
            if ai < 0 and bi < 0 and cb == '0':
                break

            if ai >= 0:
                numa = a[ai]
                ai -= 1
            else:
                numa = '0'
            
            if bi >= 0:
                numb = b[bi]
                bi -= 1
            else:
                numb = '0'
            
            cal = self.calculate[numa+numb+cb]
            nums[ni], cb = cal[0], cal[1]
            ni -= 1
        
        if nums[0] == '':
            nums = nums[1:None]
        
        return ''.join(nums)

if __name__ == '__main__':
    so = Solution()
    print(so.addBinary('11', '10'))
    print(so.addBinary('1010', '1011'))
